public class Leet688 {
    public static void main(String[] args) {
        Leet688 l = new Leet688();
        System.out.println(l.knightProbability(3,2,0,0));
    }
    static double[][][] dp;
    public double knightProbability(int n, int k, int row, int column) {
        dp = new double[k+1][n+1][n+1];
        return dfs(n,k,row,column)/Math.pow(8,k);
    }
    double dfs(int n,int k,int r,int c){
        if (r<0||c<0||r>=n||c>=n){
            return 0;
        }
        if (k==0){
            return 1.0d;
        }
        if (dp[k][r][c]!=0)
            return dp[k][r][c];
        dp[k][r][c] = dfs(n,k-1,r+2,c+1)+
                dfs(n,k-1,r+2,c-1)+
                dfs(n,k-1,r-2,c+1)+
                dfs(n,k-1,r-2,c-1)+
                dfs(n,k-1,r+1,c+2)+
                dfs(n,k-1,r+1,c-2)+
                dfs(n,k-1,r-1,c+2)+
                dfs(n,k-1,r-1,c-2);
        return dp[k][r][c];
    }
}
